package org.example.leetcode;

import com.sun.media.sound.SoftFilter;
import org.example.atomic.AtomicTest;
import org.junit.jupiter.api.Test;
import org.redisson.Redisson;

import java.util.*;

/**
 * file:ShuZu.class
 * function:
 *
 * @author shaodan wang
 * @date 2024-06-03
 */

public class ShuZu {


//    比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
//    P   A   H   N
//    A P L S I I G    //可以类似于理解为W

    public void traverNums(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        System.out.println("result-------------------------------------------");
        for (int num : nums) {
            System.out.print(num + " ");

        }
    }
//    Y   I   R

    public String convert(String s, int numRows) {
        //注意这个特殊情况，当为1的时候，只需要一行，无论是增还是减， 都会越界
        if (numRows < 2) {
            return s;
        }
        char[] charArray = s.toCharArray();
        List<StringBuilder> resultList = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            resultList.add(new StringBuilder());//初始化
        }
        int i = -1;//区域变化指针
        int flag = -1;
        for (char c : charArray) {
            if (i == 0 || i == numRows - 1) {//说明下一步要换行了
                flag = -flag;
                i = i + flag;
            }

            resultList.get(i).append(c);

        }
        StringBuilder resString = new StringBuilder();
        for (StringBuilder stringBuilder : resultList) {
            resString.append(stringBuilder.toString());

        }
        return resString.toString();
    }


    @Test
    public void testConvert() {

        System.out.println(convert("AB", 1));

    }

    //TODO 没做出来
    public String intToRoman(int num) {
        // 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中，并且按照阿拉伯数字的大小降序排列
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder stringBuilder = new StringBuilder();
        int index = 0;
        while (index < 13) {
            // 特别注意：这里是等号
            while (num >= nums[index]) {
                stringBuilder.append(romans[index]);
                num -= nums[index];
            }
            index++;
        }
        return stringBuilder.toString();
    }


    /**
     * 移除0
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
        }
        for (; slow < nums.length; slow++) {
            nums[slow] = 0;
        }
    }

    @Test
    public void testMoveZeroes() {
        int[] abc = new int[]{1, 0, 9, 7, 4, 0, 2, 3};
        moveZeroes(abc);
        for (int i : abc) {
            System.out.print(i + " ");

        }

    }

    public int removeElement(int[] nums, int val) {

        int totalVal = 0;
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            } else {
                totalVal++;
            }
        }
        return totalVal;
    }

    @Test
    public void testRemoveElement() {
        int[] nums = new int[]{3, 2, 1, 4, 5, 6, 3};
        System.out.println(removeElement(nums, 3));


    }


    /**
     * 滑动窗口，长度最小的子数组
     * 给定一个含有 n 个正整数的数组和一个正整数 target。
     * 找出该数组中满足其总和大于等于 target 的长度最小的子数组
     * [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0
     *
     * @param target
     * @param nums
     * @return
     */

    public int minSubArrayLen(int target, int[] nums) {
        //left是用来减少，right是用来增加的
        int left = 0;//左边窗口指针
        int minLen = Integer.MAX_VALUE;
        int sum = 0;
        for (int right = 0; right < nums.length; right++) { //right 右边窗口指针
            sum = sum + nums[right];
            while (sum >= target) { //说明加得太大了，或者 刚好相等，可以尝试减少了
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left++];
            }
        }
        //有可能没找到最小得序列，就返回0
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    @Test
    public void testMinSubArrayLen() {
        System.out.println(minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
    }


    /**
     * 水果成篮 滑动窗口
     * 你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，
     * 其中 fruits[i] 是第 i 棵树上的水果种类。
     * 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
     * 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
     * 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。
     * 采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
     * 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
     * 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
     *
     * @param fruits
     * @return
     */

    //意思：就是两个篮子最多能放两种类型的水果，但是可以无限放，问题是一棵树只能采摘一颗水果，且必须连续采摘，问最多能够摘多少水果。
    // [2,3,2,2,3,4] 这个 2，3，2，2.....是水果的种类 不是数量，如：2代表苹果，2代表香蕉等.......
    public int totalFruit(int[] fruits) {
        //必须连续采摘(既，最左边的树的和右边的树必须连续)
        //key存放的是篮子装的水果的类型，value存放的是，采摘的数量
        Map<Integer, Integer> cnt = new HashMap<>();
        int left = 0, ans = 0;
        for (int right = 0; right < fruits.length; ++right) {
            //右边一直走，采摘水果放在篮子里
            cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
            while (cnt.size() > 2) {
                cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
                if (cnt.get(fruits[left]) == 0) {
                    cnt.remove(fruits[left]);
                }
                ++left;
            }
            //因为每棵树只能摘一个，所以，right-left + 1是采摘的水果的数量，

            ans = Math.max(ans, right - left + 1);//每次比较，获取采摘水果的最大值
        }
        //也可以将map的每个value求和，此时求的和也是最终的答案的值
        return ans;
    }

    @Test
    public void testTotalFruit() {
//        System.out.println(totalFruit(new int[]{1,2,1}));
        System.out.println(totalFruit(new int[]{3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4}));

    }

    /**
     * 滑动窗口 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * #################################################################
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     * ------------------------------------------------------------------
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
     * ------------------------------------------------------------------
     *
     * @param s
     * @param t
     * @return
     */

    private Map<Character, Integer> ori = new HashMap<>();//存放t的映射(t为标准)
    private Map<Character, Integer> cnt = new HashMap<>();

    public String minWindow(String s, String t) {
        for (int i = 0; i < t.length(); i++) { //把t作为映射
            char tChar = t.charAt(i);
            ori.put(tChar, ori.getOrDefault(tChar, 0) + 1);
        }
        int l = 0, r = -1; //l做窗口边界，r右窗口边界
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r < sLen) {
            ++r;
            if (r < sLen && ori.containsKey(s.charAt(r))) {//找到在t中存在的字符
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {//字串找到，适当地收缩窗口
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public boolean check() { //判断cnt中是否包含所有的t中的char,且数量大于等于t中的数量
        Iterator iter = ori.entrySet().iterator();
        ori.keySet();
        ori.values();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        }
        return true;
    }


    //自己做的
    public String minWindow1(String s, String t) {
        Map<Character, Integer> tMap = new HashMap<>();
        Map<Character, Integer> sMap = new HashMap<>();
        for (char tChat : t.toCharArray()) { //建立map
            tMap.put(tChat, tMap.getOrDefault(tChat, 0) + 1);
        }
        int start = 0;//最小字串的开始位置
        int end = 0; //最小字串的结束位置
        int minLen = Integer.MAX_VALUE;//最小长度
        int l = 0;
        int r = 0;//左右指针
        while (r < s.length()) {
            if (tMap.containsKey(s.charAt(r))) {
                sMap.put(s.charAt(r), sMap.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (sContainAllt(tMap, sMap) && l <= r) {//收缩窗口
                int len = r - l + 1;
                if (len < minLen) {//最小长度
                    start = l;
                    end = r;
                    minLen = len;
                }
                if (tMap.containsKey(s.charAt(r))) {
                    sMap.put(s.charAt(l), sMap.getOrDefault(s.charAt(l), 0) - 1);
                }
                l++;
            }
            r++;//向右移动
        }
        return minLen != Integer.MAX_VALUE ? s.substring(start, end + 1) : "";
    }

    public boolean sContainAllt(Map<Character, Integer> tmap, Map<Character, Integer> smap) {
        for (Map.Entry<Character, Integer> tEntry : tmap.entrySet()) {
            if (!smap.containsKey(tEntry.getKey()) || (tEntry.getValue() > smap.get(tEntry.getKey()))) {
                return false;
            }
        }
        return true;
    }

    @Test
    public void windows1() {
        System.out.println(minWindow1("EBANC", "ABC"));
    }

    /**
     * 螺旋矩阵
     *
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int startX = 0, startY = 0;  // 每一圈的起始点 x表示行，y表示列
        int offset = 1;
        int count = 1;  // 矩阵中需要填写的数字
        int loop = 1; // 记录当前的圈数
        int i, j; // j 代表列, i 代表行;

        while (loop <= n / 2) {
            // 顶部
            // 左闭右开，所以判断循环结束时， j 不能等于 n - offset
            for (j = startY; j < n - offset; j++) {
                nums[startX][j] = count++;
            }

            // 右列
            // 左闭右开，所以判断循环结束时， i 不能等于 n - offset
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = count++;
            }

            // 底部
            // 左闭右开，所以判断循环结束时， j != startY
            for (; j > startY; j--) {
                nums[i][j] = count++;
            }

            // 左列
            // 左闭右开，所以判断循环结束时， i != startX
            for (; i > startX; i--) {
                nums[i][j] = count++;
            }
            startX++;
            startY++;
            offset++;
            loop++;
        }
        if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
            nums[startX][startY] = count;
        }
        return nums;
    }


    /**
     * 左闭右开
     *
     * @param n
     * @return
     */

    // TODO 螺旋矩阵 offset 定义错误，loop 和n的关系定义错误，奇数情况也搞错了
    public int[][] generateMatrix1(int n) {
        int[][] result = new int[n][n];
        int count = 1;
        int loop = 1;//循环
        int startX = 0, startY = 0;//每一圈的起始点 x表示行，y表示列
        int offset = 1;//每次转一圈都缩小, 左闭右开
        int i; //列
        int j; //行
        while (loop <= n / 2) {
            for (j = startY; j < n - offset; j++) {//从左到右
                result[startX][j] = count++;
            }

            for (i = startX; i < n - offset; i++) { // 在右边从上到下
                result[i][j] = count++;
            }

            //下面开始，从右到左
            for (; j > startY; j--) {
                result[i][j] = count++;
            }

            //最左边 从下到上
            for (; i > startX; i--) {
                result[i][j] = count++;
            }
            offset++;
            startY++;
            startX++;
            loop++;
        }
        if (n % 2 == 1) {//奇数情况
            result[startX][startY] = count;
        }
        return result;
    }


    @Test
    public void generateMatrix() {

        int[][] ints = generateMatrix1(5);

        for (int[] anInt : ints) {
            for (int j = 0; j < ints[0].length; j++) {
                System.out.print(anInt[j] + " ");
            }
            System.out.println("");
        }

    }


    // 错误解答
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int m = matrix.length; //行
        int n = matrix[0].length; //列
        int loop = 1; //
        int offset = 1;
        int startX = 0, startY = 0; //x为行，y为列
        int i, j;//i为行，j为列
        while (loop <= m / 2 && loop <= n / 2) {
            i = startX;
            j = startY;
            for (; j < n - offset; j++) {//左到右
                result.add(matrix[startX][j]);
            }
            for (; i < m - offset; i++) {//右边从上到下
                result.add(matrix[i][j]);
            }
            for (; j > startY; j--) {//下面从右到左
                result.add(matrix[i][j]);
            }
            for (; i > startX; i--) {//左边从下到上
                result.add(matrix[i][j]);
            }
            loop++;
            startX++;
            startY++;
            offset++;
        }
        if (m % 2 == 1) {
            result.add(matrix[startX][startY]);
        }
        return result;
    }



    //TODO 来自评论区的解答 dirNum记录的是转向次数。每次“碰壁”就转向。set记录之前走过的格子。
    public List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int m = matrix.length; //行
        int n = matrix[0].length; //列
        boolean[][] set = new boolean[m][n];//这里记录的是是否走过的格子
        //x行，y代表列
        int[][] dir = {    //不同方向 x，y 需要 加1 减1  或不变0
                {0, 1},    // {x, y}
                {1, 0},    // {x, y}
                {0, -1},   // {x, y}
                {-1, 0}    // {x, y}
        };
        int cnt = m * n; //需要行走的步数
        int i = 0, j = 0, x = 0, y = 1; //x行，y代表列
        int dirNum = 0;

        while (cnt != 0) {
            --cnt;
            ans.add(matrix[i][j]);
            set[i][j] = true;
            //该转弯了
            if (i + x < 0 || i + x >= m || j + y < 0 || j + y >= n || set[i + x][j + y]) {
                ++ dirNum;
                x = dir[dirNum % 4][0];
                y = dir[dirNum % 4][1];
            }
            i += x;
            j += y;
        }
        return ans;
    }

    @Test
    public void spiralOrder() {
        System.out.println(spiralOrder(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}));
    }


    public static void main(String[] args) {
        System.out.println(String.class.getClassLoader());
        System.out.println(ShuZu.class.getClassLoader());
        System.out.println(AtomicTest.class.getClassLoader() == ShuZu.class.getClassLoader());
        System.out.println(ShuZu.class.getClassLoader() == Redisson.class.getClassLoader());
    }
}



